Data storage systems write data to and read data from media. The data is first written to and later read from the media. Such media can include hard disks and memory. The memory can include a variety of flash memory types. Data that is written to media can contain error bits. To address the problem of error bits data can be encoded with error-correcting codes (ECC) that allow error bits to be identified and corrected at read. BCH codes are a type of error-correcting code. The acronym BCH comprises the initials of its inventors Bose, Ray-Chaudhuri and Hocquenghem. An important advantage of BCH codes is that they can be decoded via an algebraic method known as syndrome decoding. Syndromes identify error patterns of received data. Syndrome decoding enables decoding to be performed by electronic hardware which can obviate the need for a computer to perform these tasks efficiently.
BCH codes were developed in the late 1950's and early 1960's. These codes are used in satellite communications, data storage systems, digital communications and mobile communications among other technological applications. Because of its algebraic structure, a typical BCH code constructed over a finite or “Galois” field GF(2m) where m is a positive integer of at least three, can correct up to t random error bits with mt redundant bits where t is less than half of (2m−1). In particular, a (2m−1, 2m−1−mt) BCH code can encode K data bits and generate N encoded bits where K=2m−1−mt and N=2m−1.
One of the conventional methodologies that is suitable for VLSI architecture for decoding BCH codes includes three sequential stages: (1) syndrome calculation, (2) Key Equation determination, and (3) the performance of a Chien Search. Syndrome calculation based on a (2m−1)-bit received codeword will yield t syndromes that possess information related to error bit location. Additionally, the t syndromes can indicate when a received codeword is error-free and can be used to derive the aforementioned Key Equation in cases where at least some of the t syndromes are not zero.
The Key Equation is a polynomial whose order indicates the actual number of error bits that are located within a binary data block and whose roots implicitly project error bit locations. Unfortunately, such projections are nonlinear over GF(2m) (through a mapping of exponential function) and consequently the identification of error bits directly via the Key Equation is difficult. Conventional approaches use a so-called Chien search where VLSI circuits are employed to exhaustively test all bit locations with the corresponding powers as inputs so as to determine the error bit locations.
As it regards the implementation of conventional decoding methodologies such as that discussed above, the calculation of syndromes involves a fixed procedure that is defined by algebraic coding architecture, e.g., defined by BCH codes. Moreover, there are many types of methodologies that can be used to obtain the Key Equation from the obtained syndromes, such as, for example, Euclidean approaches or the use of a Berlekamp algorithm. However, when t (the number of random error bits) is small, the Key Equation can be obtained using manipulated syndromes. The execution of a Chien search requires that nonlinear mapping from each bit location is inserted into the Key Equation to determine if it satisfies the Key Equation. If a nonlinear mapping satisfies the Key Equation, then its corresponding bit location is determined to contain an error bit.
Conventional methodologies such as those discussed above can involve extensive testing of bit locations and thus exhibit less than satisfactory operating speeds (error locating time). Moreover, the hardware that is required to implement the systems can be excessive and thus manufacturing complexity and cost can be unsatisfactory. In addition, many of the conventional systems are limited as it relates to reliability, efficiency and operating range.